401. Sharik’s Letter
from Prostokvashino
“Dear Uncle Fedor!
Do not listen to this old grumpy cat.
He does not know what surprise I have prepared for him, so you can begin to
write a program for him. I increased the number of brackets for him up to 300,
the number of jobs per day up to 20, and complicated the task itself.
Now he must find the depth of the
correctly formed bracket expression . What does it mean I read in one clever
book which was lost by post officer Pechkin. The following was written there:
“Let X is a set of correctly formed
bracket expressions. The length of the correctly formed expression E is the
number of single brackets in E. The bracket depth D(E) of expression E is
defined as follows:
For example, the length of ( )(( ))(
) is 8, and the depth is 2.”
Understanding that the cat is not a
man, I give him such tasks, where the depth of expression is at least 1 and no
more than 200, and at least 2 squares with brackets. Now let he find the number
of ways to get the correct bracket sequence with given length and depth.
So hurry to send him your new
program, because now I am milking a cow only until Matroskin is busy computing.
Photo of thoughtful Matroskin is attached.
Your faithful friend and companion –
Sharik”
Input. Each line contains two numbers n and d, where n is the number
of squares with parentheses, and d is
the depth of expression. Input can contain empty lines, ignore them.
Output. For each test case print in a
separate line the number of ways to obtain the correctly formed bracket
expression of length n and depth d.
|
Sample input |
Sample output |
|
6 2 300 150 |
3 1 |
SOLUTION
dynamic programming
Algorithm
analysis
Any non-empty bracket expression A of
length n and depth no greater than d can be expressed as (X)Y, where X and
Y some expressions, possibly empty. Let the length of expression (X) equals to k. Then the length of X is k – 2, and the length of Y is n – k.
Obviously that 2 ≤ k ≤ n and k can take only even values. When k = 2 the expression X is empty, and when k = n the expression Y is
empty. Note also, since the depth of expression A is not greater than d, then the depth of X is not greater
than d – 1, and the depth of Y is not
greater than d.
Denote f(n, d) the number of ways to get a well-formed bracket expression of
length n and depth not greater than d. Then we have f(k – 2, d – 1) ways to represent the expression
X and f(n – k, d) ways to represent the expression Y. Using
the multiplication rule we can say that for a fixed k the expression (X)Y can be represented in f(k – 2, d – 1) * f(n – k, d)
ways. So
f(n, d)
= 
Since the problem requires to find
the number of ways to get a well-formed bracket expression of length n and depth exactly d, then the answer will g(n,
d) = f(n, d) – f(n, d
– 1).
Separately you must handle the
following cases:
·
If
d > n / 2, then g(n, d)
= 0;
·
If
d = n / 2, then we have a unique bracket expression (((…))), so g(n,
n / 2) = 1;
·
If
d = 1, then we have a unique bracket
expression ()()…()(), so g(n, 1) = 1;
Example
f(2, 2) = 
= f(0, 1) * f(0, 2) = 1* 1
= 1. If one can represent the bracket expression of length 2 and depth not
greater than 2 as (X)Y, then the factor f(0,
1) corresponds to the number of ways to represent X, and the factor f(0, 2) corresponds to the number of
ways to represent Y. These factors equal to one, and X and Y corresponds an
empty expression. So for f(2, 2) corresponds
only one expression ().
f(4, 2) = 
=
f(0, 1) * f(2, 2) + f(2, 1) * f(0, 2) = 1 * 1
+ 1 * 1 = 2
The summand f(0, 1) * f(2, 2) corresponds
to expression ()(), and the summand f(2,
1) * f(0, 2) corresponds to
expression (()).
f(6, 2) = 
=
f(0, 1) * f(4, 2) + f(2, 1) * f(2, 2) + f(4, 1) * f(0, 2) = 1 * 2 + 1 * 1 + 1 * 1 = 4
|
Summand |
The corresponding bracket expressions |
|
f(0, 1) * f(4, 2) |
()()(), ()(()) |
|
f(2, 1) * f(2, 2) |
(())() |
|
f(4, 1) * f(0, 2) |
(()()) |
The number of correctly formed
bracket expressions of length 6 and of depth exactly 2 equals to
g(6, 2) = f(6, 2) – f(6, 1) = 4 – 1 = 3
They are: ()(()),(())(),(()()).
Algorithm
realization
The value f(n, d) we shall keep in
array of long numbers ff.
BigInteger ff[301][151];
The function f computes the value f(n, d).
Separately handle the cases when n
< 0 or d < 0 (the function f returns 0). If n
= 0, then f(0, d) is assumed to be
equal to 1 for any d (this is the
case when either X or Y is empty).
BigInteger
f(long long n, long long d)
{
long long k;
BigInteger &s = ff[n][d];
if ((n <
0) || (d < 0)) return 0;
if (!n) return ff[n][d] = BigInteger(1);
if (ff[n][d]
>= 0) return ff[n][d];
for(s = 0, k
= 2; k <= n; k += 2)
s = s + f(k - 2,d - 1) * f(n - k,d);
return s;
}
The main
part of the program. First handle the special cases.
memset(ff,-1,sizeof(ff));
while(scanf("%lld
%lld",&n,&d) == 2)
{
if (d > n
/ 2) res = BigInteger(0); else
if ((d == n
/ 2) || (d == 1)) res = BigInteger(1); else
res = f(n,d) - f(n,d-1);
res.print();printf("\n");
}
Java realization
import java.util.*;
import java.math.*;
public class Main
{
static BigInteger dp[][];
static BigInteger f(int n, int d)
{
BigInteger s = BigInteger.ZERO;
if ((n < 0) || (d < 0)) return BigInteger.ZERO;
if (n == 0) return dp[n][d] = BigInteger.ONE;
if (dp[n][d].compareTo(BigInteger.ZERO) >= 0) return dp[n][d];
for(int k = 2; k <= n; k += 2)
s = s.add(f(k - 2,d - 1).multiply(f(n - k,d)));
return dp[n][d] = s;
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
while(con.hasNextInt())
{
int n = con.nextInt();
int d = con.nextInt();
dp = new BigInteger[n+1][d+1];
for(int i = 0; i <= n; i++)
for(int j = 0; j <= d; j++)
dp[i][j] = new BigInteger("-1");
BigInteger res = new BigInteger("0");
if (d > n / 2) res = BigInteger.ZERO; else
if ((d == n / 2) || (d == 1))
res = BigInteger.ONE; else
res = f(n,d).subtract(f(n,d-1));
System.out.println(res);
}
con.close();
}
}